Trading Independent for Synchronized Parallelism in Finite Copying Parallel Rewriting Systems

摘要

The so-called family of finite copying parallel rewriting systems is considered in this work, including well-known generative devices and transducers as for instance the deterministic tree-walking transducers, the string generating context-free hypergraph grammars, and the multiple context-free grammars. Two parameters have been defined in the literature for all of the above systems, called the degree of synchronized parallelism and the degree of independent parallelism. When constant bounds are imposed on these parameters, the subclasses of languages generated by the above systems form a two-dimensional hierarchy. In this paper we investigate the interactions between these two parameters and establish new inclusion and separation results for subclasses of the hierarchy. More precisely, for a full half of the hierarchy we provide necessary and sufficient conditions to determine when a language subclass defined by an integer bound ofron the degree of independent parallelism is included in, includes, or is incomparable with a subclass defined by a bound ofr−1 on the same parameter. This means that, in the given range, we can exactly determine which increase in the degree of synchronized parallelism must be taken in order to compensate for a reduction of one unit in the degree of independent parallelism. This solves a question left open in the literature.